package amazon;


/*
 * I will use the common "runner" algorithm. That is, make two references to the head of the list,
 * forward one of them at the pace of 1 and forward the other at pace 2. 
 * Oberserve that if the list has a loop, the runners will keep running and never hit the end.
 * During each step, check whether the two refereces are ever the same, 
 * i.e. they meet after leaving the head of list.
 * If they meet, then there must be a loop so that the faster runner catches up with the slower runner.
 * Otherwise, one runner will reach the end of loop and we know there is no loop.
 * The running time will be O(n) where n is the number of nodes in the list, because either a runner hits null,
 * which takes O(n), or the faster runner catches up with the slower runner, with the time proportional to O(n),
 * which is still O(n).
 */
public class ListLoopQuestion {

  public static class ListNode {

     public int value;

     public ListNode next;
  }
 
  public static boolean hasLoops( ListNode myList ) {
      // Trivial case.
      if (null == myList) {
          return false;
      }
      
      ListNode slow = myList, fast = myList;
      
      while (true) {
          slow = slow.next;
          if (null != fast.next) {
              fast = fast.next.next;
          } else { // fast reaches end
              return false;
          }
          
          // Either runner reaches null.
          if (fast == null || slow == null) {
              return false;
          }
          
          // They meet, loop detected.
          if (fast == slow) {
              return true;
          }
      }
      
  }

  public static void main(String[] args) {
	  int n = 10;
	ListNode head = new ListNode();
	head.value = -1;
	ListNode x = head;
	ListNode l = null;
	for (int i = 0; i < n; i++) {
		x.next = new ListNode();
		x.next.value = i;
		x = x.next;
		if (i == 5) {
			l = x;
		}
	}
	x.next = l;
//	x.next = head;
	
	System.out.println(hasLoops(head));
  }
}
